/*************************************************************************
 * File Name:    Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-6 11:32:54
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Construct Binary Tree from Preorder and Inorder Traversal
 |
 | Given preorder and inorder traversal of a tree, construct the binary tree.
 |
 | Note:
 | You may assume that duplicates do not exist in the tree.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        TreeNode *root;
        dfs(root, preorder.begin(), inorder.begin(), preorder.size());
        return root;
    }

private:    
    void dfs(TreeNode* &root, vector<int>::iterator pre_iter, vector<int>::iterator in_iter, int size)
    {
        if (size == 0) {
            root = NULL;
            return;
        }
        int left_tree_size = 0;
        
        for (vector<int>::iterator it = in_iter; it - in_iter < size; ++it) {
            if (*it == *pre_iter) break;
            ++left_tree_size;
        }
        root = new TreeNode(*pre_iter);
        dfs(root->left, pre_iter + 1, in_iter, left_tree_size);
        dfs(root->right, pre_iter + left_tree_size + 1, in_iter + left_tree_size + 1, size - left_tree_size - 1);
    }
};

int
main(int argc, char *argv[])
{
    vector<int> preorder, inorder;

    preorder.push_back(1);
    preorder.push_back(2);
    preorder.push_back(3);

    inorder.push_back(2);
    inorder.push_back(3);
    inorder.push_back(1);

    Solution sol;

    TreeNode *ans = sol.buildTree(preorder, inorder);

    return 0;
}
